UVa/10130 - SuperSale/10310.2.c

   1 /*
   2   10310 - SuperSale
   3   UVa Online Judge
   4
   5   Andrés Mejía-Posada
   6   Accepted
   7  */
   8
   9 #include <stdio.h>
  10
  11 #define MAX(a, b) ((a) > (b) ? (a) : (b))
  12
  13 #define MAXC 30
  14 #define MAXN 1000
  15
  16 int dp[MAXN][MAXC+1];
  17
  18 int main(){
  19   int T, n, i, j;
  20   scanf("%d", &T);
  21   while (T--){
  22     scanf("%d", &n);
  23     int w[n], v[n];
  24     for (i=0; i<n; ++i){
  25       scanf("%d %d", &v[i], &w[i]);
  26     }
  27
  28     for (j=0; j<=MAXC; ++j){
  29       dp[0][j] = (j < w[0] ? 0 : v[0]);
  30     }
  31
  32     for (i=1; i<n; ++i){
  33       dp[i][0] = 0;
  34       for (j=1; j<=MAXC; ++j){
  35         dp[i][j] = dp[i-1][j];
  36         if (j - w[i] >= 0){
  37           dp[i][j] = MAX(dp[i][j], dp[i-1][j-w[i]] + v[i]);
  38         }
  39       }
  40     }
  41
  42     int g, c, answer = 0;
  43     scanf("%d", &g);
  44     while (g--){
  45       scanf("%d", &c);
  46       answer += dp[n-1][c];
  47     }
  48     printf("%d\n", answer);
  49   }
  50   return 0;
  51 }